package org.ala.linshen.dp;

import java.util.Arrays;

/**
 * 给你一个非负整数数组 nums 和一个整数 target 。

 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。



 示例 1：

 输入：nums = [1,1,1,1,1], target = 3
 输出：5
 解释：一共有 5 种方法让最终目标和为 3 。
 -1 + 1 + 1 + 1 + 1 = 3
 +1 - 1 + 1 + 1 + 1 = 3
 +1 + 1 - 1 + 1 + 1 = 3
 +1 + 1 + 1 - 1 + 1 = 3
 +1 + 1 + 1 + 1 - 1 = 3
 示例 2：

 输入：nums = [1], target = 1
 输出：1


 提示：

 1 <= nums.length <= 20
 0 <= nums[i] <= 1000
 0 <= sum(nums[i]) <= 1000
 -1000 <= target <= 1000

 * @author ala
 * @date 2024-09-30 14:13
 */
public class Q494 {

    public static void main(String[] args) {
        Q494 q = new Q494();

        int[] nums = {1,1,1,1,1};
        int target = 3;

        System.out.println(q.findTargetSumWays(nums, target));
    }

    public int findTargetSumWays(int[] nums, int target) {
        return V1(nums, target);
    }
    /**
     *  1）假设被负的数的和是：p
     *      (sum - p) - p = target
     *                 2p = sum - target
     *                  p = (sum - target) / 2
     *      其中：sum - target 必须是偶数，且必须 >= 0
     *      问题转化为：从 nums 中取数，和为 p
     *  2）0-1 背包
     *      dp[i]表示：和为i的方案数
     *      dp[i] = dp[i - n] + 1  n为遍历每个数
     */
    protected int V1(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int p = sum - target;
        if (p < 0 || (p & 1) == 1) {return 0;}
        p >>= 1;

        int[] dp = new int[p + 1];
        dp[0] = 1;
        for (int n : nums) {
            for (int i = p ; i >= n ; i--) {
                dp[i] += dp[i - n];
            }
        }
        return dp[p];
    }
}
